Abstract: "We develop a framework for sampling from discrete distributions on the $n$-dimensional hypercube by sampling from continuous distributions obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions, the result of the convolution is well-conditioned log-concave, whenever the Gaussian's variance is above a constant threshold. We plug in off-the-shelf continuous sampling methods into our framework to obtain novel discrete sampling algorithms. To bound the propagation of error in our framework, we show a stronger approximation guarantee for the state-of-the-art parallel continuos sampling algorithms for well-conditioned log concave distributions introduced by Shen and Lee.
As our main application, we resolve open questions raised by Anari, Hu, Saberi, and Schild on parallel sampling algorithms for distributions which admit parallel counting algorithms. We show that a wide class of distributions, which includes determinantal point processes and directed Eulerian tours, can be sampled from using RNC algorithms, that is, in polylog$n$ rounds using poly($n$) processors where $n$ is roughly the size or bit-complexity of one sample."
Based on joint works with Nima Anari, Sinho Chewi, Yizhi Huang, Tianyu Liu, Brian Xu, Catherine Yu.